import Range from './Range'
import assert from 'assert';

function fixChild(parent,oldNode,newNode){
    if (parent.left===oldNode) parent.left=newNode;
    else if (parent.right===oldNode) parent.right=newNode;
    else if (parent===oldNode.owner) parent.root=newNode;
    else throw new Error("invalid node child");
    newNode.parent=parent;
    oldNode.parent=newNode;
}

export class BSTNode{

    constructor(parent,value){
        this.parent=parent;
        this.owner=parent.owner;
        this.value=value;
    }

    insert(value){
        if (this.lt(value,this.value)){
            if (this.left) return this.left.insert(value);
            else return this.left=this.owner.newNode(this,value);
        }else{
            if (this.right) return this.right.insert(value);
            else return this.right=this.owner.newNode(this,value);
        }
    }

    remove() {
        let node;
        if (this.left != null && this.right != null) {
            node=this.findReplacement();
            node=this.replaceNode(node);
        } else if (this.right != null) {
            node=this.replaceTree(this.right);
        } else {
            node=this.replaceTree(this.left);
        }
        if (node&&node!=this){
            node.remove();
        }
    }

    replaceTree(replacement) {
        if (this.parent.left == this) this.parent.left = replacement;
        else if (this.parent.right == this) this.parent.right = replacement;
        else if (this.parent.root == this) this.parent.root = replacement;
        if (replacement) replacement.parent=this.parent;
    }

    replaceNode(replacement){
        this.value=replacement.value;
        return replacement;
    }

    findReplacement(){
        let node=this.left;
        while(node.right) node=node.right;
        return node;
    }

    lt(l,r){return this.owner.comp(l,r);}
    gt(l,r){return this.owner.comp(r,l);}
    le(l,r){return !this.owner.comp(r,l);}
    ge(l,r){return !this.owner.comp(l,r);}
    lc(l,r,include){return include?this.le(l,r):this.lt(l,r);}
    gc(l,r,include){return include?this.ge(l,r):this.gt(l,r);}

    rotate(){
        let parent = this.parent;
        if (parent.left===this) {
            parent.left=this.right;
            if (this.right) this.right.parent=parent;
            this.right=parent;
            fixChild(parent.parent,parent,this);
        }else if (parent.right===this) {
            parent.right=this.left;
            if (this.left) this.left.parent=parent;
            this.left=parent;
            fixChild(parent.parent,parent,this);
        }else{
            throw "root node cannot rotate";
        }
        return this;
    }

    visit(cb,order,depth=0){
        if (order===-1) cb(this,depth);
        if (this.left) this.left.visit(cb,order,depth+1);
        if (order===0) cb(this,depth);
        if (this.right) this.right.visit(cb,order,depth+1);
        if (order===1) cb(this,depth);
    }

    query(range,cb,depth){
        if (this.left&&range.gcMin(this.value)) this.left.query(range,cb,depth+1);
        if (range.inRange(this.value)) cb(this,depth);
        if (this.right&&range.lcMax(this.value)) this.right.query(range,cb,depth+1);
    }

    isRoot(){
        return this.parent==this.owner;
    }

    get sibling(){
        if (this.parent===this.owner) return;
        else if (this.parent.left===this) return this.parent.right;
        else if (this.parent.right===this) return this.parent.left;
    }

    get grandparent(){
        if (this.parent===this.owner) return;
        return this.parent.parent;
    }

    get uncle(){
        if (this.parent===this.owner) return;
        return this.parent.sibling;
    }

    assert(){
        if (this.left!=null) {
            assert.equal(this.left.parent,this);
            assert(this.le(this.left.value,this.value));
        }
        if (this.right!=null) {
            assert.equal(this.right.parent,this);
            assert(this.ge(this.right.value,this.value));
        }
    }
}


export class BSTree{

    constructor(comp){
        this.comp=comp||((l,r)=>l<r);
        this.owner=this;
        this.size=0;
    }

    nodeType(){
        return BSTNode;
    }

    newNode(parent,value){
        return new (this.nodeType())(parent,value)
    }

    insert(value){
        let node;
        if (this.root==null) node=this.root=this.newNode(this,value);
        else node=this.root.insert(value);
        if (node) ++this.size;
        this.assertSize();
        return node;
    }



    query(range){
        if (!(range instanceof Range)) range=new Range(range,this.comp);
        let out=[];
        if (this.root) this.root.query(range,e=>{out.push(e)});
        return out;
    }

    queryOne(value){
        return this.query(new Range({eq:value},this.comp))[0];
    }

    remove(value){
        let node=this.queryOne(value);
        if (node==null) return;
        node.remove();
        return node;
    }

    visit(cb,order=0){
        if (this.root) this.root.visit(cb,order);
    }

    assertSize(){
        let c=0;
        this.visit(e=>{++c});
        assert.equal(c,this.size);
    }

    assert(){
        if (this.root) this.root.assert();
    }
}